public class MaxPQ<Key extends Comparable<Key>> {
	private Key[] pq;
	private int N = 0;

	public MaxPQ (int max) {
		pq = (Key[]) new Comparable[max+1]; //max+1 leaves one slot wasted memory, but saves a few calculations with every "step" taken through the three.
	}

	public boolean isEmpty () {
		return this.N==0;
	}

	public int size (){
		return this.N;
	}

	public void insert (Key k) {
		pq[++N] = k;
		swim(N);
	}

	public Key eatMax() {
		Key max = pq[1];
		swap(1, N);
		pq[N--] = null;
		drown(1);
		return max;
	}

	private boolean less (int i, int j) {
		return pq[i].compareTo(pq[j]) < 0;
	}

	private void swap (int i, int j) {
		Key t = pq[i];
		pq[i] = pq[j];
		pq[j] = t;
	}

	private void swim (int k) {
		while (k>1 && less(k/2, k)) { //as long as my parents<me, swap me with my parents
			swap(k/2, k);
		}
	}

	private void drown (int k) {
		while (2*k <= N) { 
			int j = 2*k;
			if (j<N && less(j, j+1)) j++; 	//pick my bigest child!
			if (!less(k, j)) break; 	//if my biggest child<=me, we're done
			swap(k, j); 			//else swap me and my child
			k=j; 				//I get a second childhood!
		}
	}

	public Key[] getList() {
		return pq;
	}
}
